package red.book._2._4;

import edu.princeton.cs.algs4.IndexMinPQ;
import edu.princeton.cs.algs4.Quick;
import red.book._2._1.Example;

/**
 * 二叉堆
 * @author wangbingwu
 *
 * @param <Key>
 */
public class MaxPQ <Key extends Comparable<Key>>{
	private Key[] arr;
	private int N = 0;
	
	@SuppressWarnings("unchecked")
	public MaxPQ(int max) {
		arr = (Key[])new Comparable[max + 1];
	}
	
	private void swim(int k) {
		while(k > 1) {
			if (Example.less(arr[k/2], arr[k])) {
				Example.exch(arr, k, k/2);
				k = k/2;
			}else break; //这里书中没有， 但是应该break, 否者会死循环吧。
		}
	}
	
	public int size() {
		return N;
	}
	
	private void sink(int k) {
		
		while(2 * k <= N) {
			int j = 2 * k;
			if (j < N && Example.less(arr[j], arr[j + 1])) { //这里是较大值和
				j ++;
			}
			
			if(!Example.less(arr[k], arr[j])) {
				break;	//注意无论是swim还是sink都要有break,会避免多余的循环或者死循环。
			}
			Example.exch(arr, k, j);
			k = j; //这里也要注意k要随着循环在改变。
		}
	}
	
	public Key delMax(){
		Key result = arr[1];
		arr[1] = arr[N--]; //书中是交换， 但应该不用，直接覆盖。
		arr[N + 1]  = null;
		sink(1);
		return result;
	}
	
	/**
	 * 这里忽略了扩容等问题
	 * @param key
	 */
	public void insert(Key key) {
		arr[++N] = key; //注意N的有效值是从1开始的。
		swim(N);
	}
	
	
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		MaxPQ<Integer> pq = new MaxPQ<>(3);
		pq.insert(2);
		pq.insert(1);
		pq.insert(3);
		int size = pq.size();
		for(int i = 0;i < size; i++) {
			System.out.println(pq.delMax());
		}
		
		Comparable[] a = new Comparable[3];
		Quick.sort(a);
		int count = 1; // Assume a.length > 0.
		for (int i = 1; i < a.length; i++)
		if (a[i].compareTo(a[i-1]) != 0)
		count++;
		System.out.println(count);
	}
}
